package sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2020/11/10
 * Time:0:27
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[10];
        Random r = new Random();

        for(int ii = 0;ii<10;ii++){
            for(int i = 0;i<arr.length;i++){
                arr[i] = r.nextInt(50);
            }
            quickSort(arr);
            System.out.println(Arrays.toString(arr));
        }

    }

    //得到支点下标
    public static int partion(int[] arr,int low,int high){
        int tmp = arr[low];
        while(low<high){
            //high位置值大于tmp，high自减
            while(low<high&&arr[high]>tmp){
                high--;
            }
            //如果low和high相等，直接退出循环，否则将high位置值赋给low位置，然后low自增
            if(low == high){
                break;
            }else{
                arr[low] = arr[high];
                low++;
            }
            //位置值小于tmp，low自增
            while(low<high&&arr[low]<tmp){
                low++;
            }
            //如果low和high相等，直接退出循环，否则将low位置值赋给high位置，然后high自减
            if(low == high){
                break;
            }else{
                arr[high] = arr[low];
                high--;
            }
        }
        //将支点值赋给high位置
        arr[high] = tmp;
        //返回支点下标
        return high;
    }

    //非递归排序
    public static void quickSort(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int low = 0;
        int high = arr.length-1;
        //获取支点下标
        int par = partion(arr,low,high);
        //如果区间长度大于1，则区间两端下标入栈
        if(par>low+1){
            stack.push(low);
            stack.push(par-1);
        }
        if(par+1<high){
            stack.push(par+1);
            stack.push(high);
        }
        //栈不为空，继续操作
        while(!stack.isEmpty()){
            //获取栈中区间下标
            high = stack.pop();
            low = stack.pop();
            //获取支点下标
            par = partion(arr,low,high);
            //如果区间长度大于1，则区间两端下标入栈
            if(par>low+1){
                stack.push(low);
                stack.push(par-1);
            }
            if(par+1<high){
                stack.push(par+1);
                stack.push(high);
            }
        }
    }
}
